package com.cango.student.algorithm;

import java.util.LinkedList;

/**
 * 链表反转
 * LinkedList的反转
 */
public class NodeSort {
    static class Node {
        Integer data;
        Node next;
    }

    /**
     * 链表反转
     */
    public static void main(String[] args) {
        Node linkNode1 = new Node();
        linkNode1.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 2;
        Node linkNode3 = new Node();
        linkNode3.data = 3;
        Node linkNode4 = new Node();
        linkNode4.data = 4;
        Node linkNode5 = new Node();
        linkNode5.data = 5;
        Node linkNode6 = new Node();
        linkNode6.data = 6;

        linkNode1.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;
        linkNode5.next = linkNode6;

        train2(linkNode1);

        System.out.print(linkNode6.next.data);
    }

    /**
     * 递归方法反转
     *
     * @param node
     * @return
     */
    static Node reverseLinkedList(Node node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            Node headNode = reverseLinkedList(node.next);
            node.next.next = node;
            node.next = null;
            return headNode;
        }
    }

    /**
     * LinkedList的反转
     */
    static LinkedList reverseLinkedList(LinkedList linkedList) {
        LinkedList<Object> newLinkedList = new LinkedList<>();
        for (Object object : linkedList) {
            newLinkedList.add(0, object);
        }
        return newLinkedList;
    }

    public static Node train(Node node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            Node now = train(node.next);
            node.next.next = node;
            node.next = null;
            return now;
        }
    }

    public static Node train2(Node node) {
        if (node == null)
            return null;

        Node pre = node;
        Node cur = node.next;
        Node next;

        while (cur != null) {
            next = cur.next;

            cur.next = pre;
            pre = cur;
            cur = next;
        }

        node.next = null;

        return  pre;
    }
}
